package HuffmanTree;

/**
 * huffmanTree.java        
 * Fecha: 21/09/12
 * Carnet: 11033
 * Modificado Por: Juan Pablo Argueta Cortés
 * NOTA: Tomado de los ejemplos del Libro Java Structure de Duane A. Bailey
 * 
 * Clase que implementa un huffmanTree a partir de BinaryTree.
 * @version $Id: BinaryTree.java 34 2007-08-09 14:43:44Z bailey $
 * @author, 2001 duane a. bailey
 */
public class huffmanTree implements Comparable<huffmanTree>
{
    private BinaryTree<node> empty;
    private BinaryTree<node> root; // root of tree
    private int totalWeight;     // weight of tree
    
    /**
     * Construye un huffmanTree con un nodo asociado a un caracter.
     * @post Construye un huffmanTree con un nodo asociado a un caracter.
     * @param e nodo con el caracter asociado
     */
    public huffmanTree(node e)
    // post: construct a node with associated character
    {
        empty = new BinaryTree<node>();
        root = new BinaryTree<node>(e,empty,empty);
        totalWeight = e.getFrecuency();
    }
    
    /**
     * Une dos huffmanTree en uno nuevo con el valor de la suma de los dos
     * @pre Los huffmanTree a unir no deben ser null
     * @post Une dos huffmanTree en uno nuevo con el valor de la suma de los dos
     * @param left
     * @param right 
     */
    public huffmanTree(huffmanTree left, huffmanTree right)
    // pre: left and right non-null
    // post: merge two trees together and total weights
    {
        this.totalWeight = left.getTotalWeight() + right.getTotalWeight();
        root = new BinaryTree<node>(new node(this.totalWeight),left.getRoot(),right.getRoot());
    }
    
    /**
     * Devuelve el valor del huffmanTree
     * @post Devuelve el valor del huffmanTree
     * @return this.totalWeight el valor del huffmanTree
     */
    public int getTotalWeight()
    {
        return this.totalWeight;
    }
    
    /**
     * Devuelve la raiz del huffmanTree
     * @post Devuelve la raiz del huffmanTree
     * @return this.root la raiz del huffmanTree
     */
    public BinaryTree<node> getRoot()
    {
        return this.root;
    }
    
    /**
     * Compara dos huffmanTree
     * @pre los huffmanTree no son null
     * @post Regresa un entero que refleja la relación entre los valores de dos huffmanTree
     * @param other
     * @return >0 si el primero es mayor al segundo
     *         =0 si ambos poseen el mismo valor
     *         <0 si el segundo es mayor al primero
     */
    public int compareTo(huffmanTree other)
    // pre: other is not null
    // post: return integer reflecting relation between values
    {
        huffmanTree that = (huffmanTree)other;
        return this.totalWeight - that.getTotalWeight();
    }
    
    /**
     * Imprime los caracteres asociados al huffmanTree
     */
    public void print()
    // post: print out strings associated with characters in tree
    {
        print(this.root,"");
    }
    
    /**
     * Imprime una cadena con los códigos asociados a los caracteres
     * del huffmanTree, separados por el caracter dado.
     * @post cadena con los códigos asociados a los caracteres
     * del huffmanTree, separados por el caracter dado.
     * @param r HuffmanTree a codificar
     * @param representation Caracter con el cual se separaran los caracteres
     */
    protected void print(BinaryTree<node> r, String representation)
    // post: print out strings associated with chars in tree r,
    //       prefixed by representation
    {
        if (!r.left().isEmpty())
        {   // interior node
            print(r.left(),representation+"0"); // append a 0
            print(r.right(),representation+"1"); // append a 1
        } else { // node; print encoding
            node e = r.value();
            System.out.println("El código de la letra "+e.getChar()+" es "+
               representation+" (Frecuencia: "+e.getFrecuency()+")");
        }
    }
    
    /**
     * Decodifica un mensaje de acuerdo al algoritmo de huffman
     * @param codigo codigo a decodificar 
     * @return mensaje El mensaje decodificado
     * @throws Exception En caso de que sea un código incorrecto
     */
    public String decode(String codigo) throws Exception{
        String mensaje = "";
        BinaryTree<node> aux = this.getRoot();
        for (int i=0;i<codigo.length();i++){
            String caracter = ""+codigo.charAt(i);
            if (caracter.equals("0")){
                if (!aux.left().isEmpty()){
                    if((aux.left().left().isEmpty())&&(aux.left().right().isEmpty())){
                        char c = aux.left().value().getChar();
                        mensaje += "" + c;
                        aux = this.getRoot();
                    } else {
                        aux = aux.left();
                    } 
                }
            } else if(caracter.equals("1")){
                if (!aux.right().isEmpty()){
                    if((aux.right().right().isEmpty())&&(aux.right().left().isEmpty())){
                        char c = aux.right().value().getChar();
                        mensaje += "" + c;
                        aux = this.getRoot();
                    } else {
                        aux = aux.right();
                    } 
                }
            } else {
                throw new Exception();
            } 
        }
        return mensaje;
    }    
}

/*
If a woodchuck could chuck wood!
*/
/*
    Encoding of ! is 0000 (frequency was 1)
    Encoding of a is 00010 (frequency was 1)
    Encoding of l is 00011 (frequency was 1)
    Encoding of u is 001 (frequency was 3)
    Encoding of d is 010 (frequency was 3)
    Encoding of k is 0110 (frequency was 2)
    Encoding of w is 0111 (frequency was 2)
    Encoding of I is 10000 (frequency was 1)
    Encoding of f is 10001 (frequency was 1)
    Encoding of h is 1001 (frequency was 2)
    Encoding of c is 101 (frequency was 5)
    Encoding of   is 110 (frequency was 5)
    Encoding of o is 111 (frequency was 5)
    Old length=256 new length=111 57% compression.
*/

